//你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能
//折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。 
//
// 如果你能使这个正方形，则返回 true ，否则返回 false 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: matchsticks = [1,1,2,2,2]
//输出: true
//解释: 能拼成一个边长为2的正方形，每边两根火柴。
// 
//
// 示例 2: 
//
// 
//输入: matchsticks = [3,3,3,3,4]
//输出: false
//解释: 不能用所有火柴拼成一个正方形。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= matchsticks.length <= 15 
// 1 <= matchsticks[i] <= 10⁸ 
// 
// Related Topics 位运算 数组 动态规划 回溯 状态压缩 👍 267 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Map;

public class _473_MatchsticksToSquare {
    public static void main(String[] args) {
        Solution solution = new _473_MatchsticksToSquare().new Solution();
//        int[] matchsticks = {1, 1, 2, 2, 2};
        int[] matchsticks = {3, 3, 3, 3, 4};
//        int[] matchsticks = {5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3};
        System.out.println(solution.makesquare(matchsticks));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean makesquare(int[] matchsticks) {
            int sum = Arrays.stream(matchsticks).sum();
            double one = sum / 4.0;
            if ((int) one != sum / 4) return false;
            int bian = sum / 4;
            int[] edge = new int[4];
            Arrays.sort(matchsticks);
            return dfs(0, matchsticks, edge, bian);
        }

        private boolean dfs(int index, int[] matchsticks, int[] edge, int len) {
            if (index >= matchsticks.length) return true;

            for (int i = 0; i < edge.length; i++) {
                edge[i] += matchsticks[index];
                if (edge[i] <= len && dfs(index + 1, matchsticks, edge, len)) {
                    return true;
                }
                edge[i] -= matchsticks[index];
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}